//https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/?envType=daily-question&envId=2023-10-21



class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        vector<bool> visited(n, false);
        long long pairs = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                unordered_set<int> connectedNodes;
                dfs(graph, visited, i, connectedNodes);
                long long connectedSize = connectedNodes.size();
                pairs += connectedSize * (n - connectedSize);
            }
        }

        return pairs / 2;
    }

private:
    void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node, unordered_set<int>& connectedNodes) {
        visited[node] = true;
        connectedNodes.insert(node);
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(graph, visited, neighbor, connectedNodes);
            }
        }
    }
};
